package arithmetic.demo15;


import java.util.*;

/**
 * 题目: bfs最短路径_最小基因变化
 */

class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        if (bank.length == 0)
            return -1;

        char[] chs = { 'A', 'C', 'G', 'T' };
        // 初始化
        // 验证有效
        Set<String> bankHash = new HashSet<>();
        // 去重
        Set<String> hash = new HashSet<>();

        Queue<String> queue = new LinkedList<>();

        // 先将基因库加入到哈希
        for(int i =0 ; i< bank.length; i++){
            bankHash.add(bank[i]);
        }

        int ret = 0;
        // 初始字符串加入队列
        queue.add(startGene);
        hash.add(startGene);

        while (!queue.isEmpty()) {
            int sz = queue.size();
            // 先走当前一层
            for (int i = 0; i < sz; i++) {
                String str = queue.poll();

                // 如果遍历到结果就返回
                if (endGene.equals(str))
                    return ret;
                // 开始遍历
                for (int k = 0; k < 8; k++) {
                    // 遍历4种不同的字符， 每个位置进行修改
                    for (int j = 0; j < 4; j++) {
                        String newStr = str.substring(0, k) + chs[j] + str.substring(k + 1, 8);
                        // 如果包含就加入队列
                        if (!hash.contains(newStr) && bankHash.contains(newStr)) {
                            queue.add(newStr);
                            // 加入过就进入哈希
                            hash.add(newStr);
                        }
                    }

                }
            }

            // 增加一次变化
            ret++;
        }

        return -1;
    }
}

class Test {
    public static void main(String[] args) {
        String[] strs = {"AAAAAAAA","AAAAAAAC","AAAAAACC","AAAAACCC","AAAACCCC","AACACCCC","ACCACCCC","ACCCCCCC","CCCCCCCA"};
        Solution solution = new Solution();
        System.out.println(solution.minMutation("AAAAAAAA", "CCCCCCCC", strs));

    }
}